
/*
 * @lc app=leetcode.cn id=126 lang=cpp
 *
 * [126] 单词接龙 II
 *
 * https://leetcode.cn/problems/word-ladder-ii/description/
 *
 * algorithms
 * Hard (40.72%)
 * Likes:    580
 * Dislikes: 0
 * Total Accepted:    46.9K
 * Total Submissions: 115K
 * Testcase Example:  '"hit"\n"cog"\n["hot","dot","dog","lot","log","cog"]'
 *
 * 按字典 wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的 转换序列 是形式上像 beginWord ->
 * s1 -> s2 -> ... -> sk 这样的单词序列，并满足：
 *
 *
 *
 *
 * 每对相邻的单词之间仅有单个字母不同。
 * 转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词。注意，beginWord 不必是字典 wordList
 * 中的单词。
 * sk == endWord
 *
 *
 * 给你两个单词 beginWord 和 endWord ，以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord
 * 的 最短转换序列 ，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, ..., sk]
 * 的形式返回。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：beginWord = "hit", endWord = "cog", wordList =
 * ["hot","dot","dog","lot","log","cog"]
 * 输出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
 * 解释：存在 2 种最短的转换序列：
 * "hit" -> "hot" -> "dot" -> "dog" -> "cog"
 * "hit" -> "hot" -> "lot" -> "log" -> "cog"
 *
 *
 * 示例 2：
 *
 *
 * 输入：beginWord = "hit", endWord = "cog", wordList =
 * ["hot","dot","dog","lot","log"]
 * 输出：[]
 * 解释：endWord "cog" 不在字典 wordList 中，所以不存在符合要求的转换序列。
 *
 *
 *
 *
 * 提示：
 *
 *
 * 1 <= beginWord.length <= 5
 * endWord.length == beginWord.length
 * 1 <= wordList.length <= 500
 * wordList[i].length == beginWord.length
 * beginWord、endWord 和 wordList[i] 由小写英文字母组成
 * beginWord != endWord
 * wordList 中的所有单词 互不相同
 *
 *
 *
 *
 */

// @lc code=start
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string> &wordList) {
        vector<vector<string>> ans;
        unordered_set<string> dict;
        // 构造dict
        for (const auto &w : wordList) {
            dict.insert(w);
        }
        if (!dict.count(endWord)) {
            return ans;
        }
        dict.erase(beginWord);
        dict.erase(endWord);
        // q1和q2是分别从起始节点和终止节点进行搜索
        unordered_set<string> q1{beginWord}, q2{endWord};
        unordered_map<string, vector<string>> next;
        bool reversed = false, found = false;
        while (!q1.empty()) {
            unordered_set<string> q;
            for (const auto &w : q1) {
                string s = w;
                for (size_t i = 0; i < s.size(); ++i) {
                    char ch = s[i];
                    for (int j = 0; j < 26; ++j) {
                        s[i] = j + 'a';
                        if (q2.count(s)) {
                            reversed ? next[s].push_back(w) : next[w].push_back(s);
                            found = true;
                        }
                        if (dict.count(s)) {
                            reversed ? next[s].push_back(w) : next[w].push_back(s);
                            q.insert(s);
                        }
                    }
                    s[i] = ch;
                }
            }
            if (found) {
                break;
            }
            for (const auto &w : q) {
                dict.erase(w);
            }
            if (q.size() <= q2.size()) {
                q1 = q;
            }
            else {
                reversed = !reversed;
                q1 = q2;
                q2 = q;
            }
        }
        if (found) {
            vector<string> path = {beginWord};
            backtracking(beginWord, endWord, next, path, ans);
        }
        return ans;
    }

    // 辅函数
    void backtracking(const string &src, const string &dst, unordered_map<string, vector<string>> &next, vector<string> &path,
                      vector<vector<string>> &ans) {
        if (src == dst) {
            ans.push_back(path);
            return;
        }
        for (const auto &s : next[src]) {
            path.push_back(s);
            backtracking(s, dst, next, path, ans);
            path.pop_back();
        }
    }
};

/* int main() {
    Solution Instance;
    string beginWord = "hit";
    string endWord = "cog";
    vector<string> wordList{"hot", "dot", "dog", "lot", "log", "cog"};
    vector<vector<string>> ans;
    ans = Instance.findLadders(beginWord, endWord, wordList);
    for (auto row : ans) {
        for (auto item : row) {
            cout << item << " ";
        }
        cout << endl;
    }
    return 0;
} */
// @lc code=end
